package com.da.javatest.niuke.baodian;

/**
 * @author chenlida
 * @date 2020/10/9 15:56
 * https://www.nowcoder.com/practice/7f0661ace6df48d0af3f924950d57126?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C39GoUpstairs {
    public static int countWays(int n) {
        int i1 = 1;
        int i2 = 2;
        int i3 = 4;
        int result = 0;
        if (n == 1) {
            return i1;
        }
        if (n == 2) {
            return i2;
        }
        if (n == 3) {
            return i3;
        }
        for (int i = 4; i <= n; i++) {
            result = ((i1 + i2) % 1000000007 + i3) % 1000000007;
            i1 = i2;
            i2 = i3;
            i3 = result;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(countWays(4));
        System.out.println(countWays(5));
    }
}
